package Mylrucache;

import java.util.HashMap;
import java.util.Map;

public class MyLRUCache {
    static class DLinkedNode {
        public int key;
        public int value;
        public DLinkedNode prev;
        public DLinkedNode next;
        public DLinkedNode() {

        }
        public DLinkedNode(int key,int value) {
            this.key=key;
            this.value=value;
        }

        public int getKey() {
            return key;
        }

        public int getValue() {
            return value;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public void setValue(int value) {
            this.value = value;
        }
    }
    public DLinkedNode head;
    public DLinkedNode tail;
    public int usedSize;
    public int capacity=3;
    public Map<Integer,DLinkedNode> cache=new HashMap<>();
    public MyLRUCache() {
        head=new DLinkedNode();
        tail=new DLinkedNode();
        tail.prev=head;
        head.next=tail;
    }
    public void put(int key,int val) {
        DLinkedNode node = cache.get(key);
        if(node == null) {
            DLinkedNode dLinkedNode=new DLinkedNode(key,val);
            cache.put(key,dLinkedNode);
            addToTail(dLinkedNode);
            usedSize++;
            if(usedSize>capacity) {
                DLinkedNode remNode=removeNode();
                cache.remove(remNode.key);
                usedSize--;
            }
        }
        else {
            node.value=val;
            MoveToTail(node);
            usedSize++;
        }
    }

    /**
     * 将指定节点移动到尾节点
     * @param node
     */
    private void MoveToTail(DLinkedNode node) {
        DLinkedNode prev=node.prev;
        DLinkedNode next=node.next;
        prev.next=next;
        next.prev=prev;
        node.prev=node.next=null;
        addToTail(node);
    }

    /**
     * 删除头节点
     * @return
     */
    private DLinkedNode removeNode() {
        DLinkedNode rem=head.next;
        head.next=rem.next;
        rem.next.prev=head;
        rem.next=rem.prev=null;
        return rem;
    }

    /**
     * 在尾节点添加节点
     * @param dLinkedNode
     */
    private void addToTail(DLinkedNode dLinkedNode) {
        dLinkedNode.prev=tail.prev;
        tail.prev.next=dLinkedNode;
        dLinkedNode.next=tail;
        tail.prev=dLinkedNode;
    }
}
